package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author 谭继好
 * @Description
 * @date 2024-04-16 21:57
 */
public class Main {

    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            char[] arr = strs[i].toCharArray();
            Arrays.sort(arr);
            String s = new String(arr);
            List<String> temp = map.getOrDefault(s, new ArrayList<>());
            temp.add(strs[i]);
            map.put(s, temp);
        }
        List<List<String>> res = new ArrayList<>();
        // 遍历map集合
        for (String s : map.keySet()) {
            res.add(map.get(s));
        }
        return res;
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            int beg = i + 1, end = nums.length - 1;
            while (beg < end) {
                if(nums[beg] + nums[end] == -nums[i]) {
                    temp.add(nums[beg]); temp.add(nums[end]); temp.add(nums[i]);
                    res.add(new ArrayList<>(temp));
                    temp = new ArrayList<>();
                    while (beg < end && nums[beg] == nums[beg + 1]) beg++;
                    while (end > beg && nums[end] == nums[end - 1]) end--;
                    beg++; end--;
                } else if (nums[beg] + nums[end] < -nums[i]) {
                    beg++;
                } else {
                    end--;
                }
            }
            while (i < nums.length - 2 && nums[i] == nums[i + 1]) i++;
        }
        return res;
    }

    public static void main(String[] args) {
//        int[] arr = new int[]{-1,0,1,2,-1,-4};
//        List<List<Integer>> list = threeSum(arr);
//        for (List<Integer> integers : list) {
//            System.out.println(integers);
//        }
    }
}
